package offer_test_40;

import struct.BinaryTreeNode;

//输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）
//形成树的一条路径，最长路径的长度为树的深度。
//Q2输入一棵二叉树的根结点，判断是否为平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差
//不超过1，那么它就是平衡二叉树。
public class nineteen_DepthOfBinaryTree {
	public static void main(String[] args) {
		BinaryTreeNode root = new BinaryTreeNode();
		BinaryTreeNode node1 = new BinaryTreeNode();
		BinaryTreeNode node2 = new BinaryTreeNode();
		BinaryTreeNode node3 = new BinaryTreeNode();
		BinaryTreeNode node4 = new BinaryTreeNode();
		BinaryTreeNode node5 = new BinaryTreeNode();
		BinaryTreeNode node6 = new BinaryTreeNode();
//		BinaryTreeNode node7 = new BinaryTreeNode();
		root.leftNode = node1;
		root.rightNode = node2;
		node1.leftNode = node3;
		node1.rightNode = node4;
		node2.rightNode = node5;
		node4.leftNode = node6;
//		node6.leftNode = node7;
		root.value = 1;
		node1.value = 2;
		node2.value = 3;
		node3.value = 4;
		node4.value = 5;
		node5.value = 6;
		node6.value = 7;
//		node7.value = 8;
		System.out.println(questTwo(root));
	}

	public static int getDepth(BinaryTreeNode node) {
		int depth = 0;
		if (node != null) {
			depth++;
		}
		if (node.leftNode != null && node.rightNode == null) {
			depth += getDepth(node.leftNode);
		}
		if (node.rightNode != null && node.leftNode == null) {
			depth += getDepth(node.rightNode);
		}
		if (node.rightNode != null && node.leftNode != null) {
			depth += Math
					.max(getDepth(node.leftNode), getDepth(node.rightNode));
		}
		return depth;
	}

	public static int getDepth2(BinaryTreeNode node) {
		if (node == null) {
			return 0;
		}
		int left = getDepth2(node.leftNode);
		int right = getDepth2(node.rightNode);
		return (left > right) ? (left + 1) : (right + 1);
	}

	// 采用后序遍历，每个节点访问一次，性能好于求深度的方法。书上参考C++解法
	public static boolean quest2(BinaryTreeNode node, int[] depth) {
		if (node == null) {
			depth[0] = 0;
			return true;
		}
		int[] left = new int[1];
		int[] right = new int[1];
		if (quest2(node.leftNode, left) && quest2(node.rightNode, right)) {
			int dif = left[0] - right[0];
			if (dif < -1 || dif > 1) {
				return false;
			} else {
				depth[0] = Math.max(right[0], left[0]) + 1;
				return true;
			}
		}
		return false;
	}
	// 采用后序遍历，每个节点访问一次，性能好于求深度的方法。递归后序遍历，
	//如果为平衡二叉树，则return maxdepth否则返回-1
	//最后输出若不为-1则是平衡的。
	public static int questTwo(BinaryTreeNode node) {
		if (node == null) {
			return 0;
		}
		int left = questTwo(node.leftNode);
		int right = questTwo(node.rightNode);
		int mis=left-right;
		if(mis<-1||mis>1){
			return -1;
		}else{
			if(right==-1||left==-1){
				return -1;
			}
			return Math.max(right, left)+1;
		}
	}
}
